namespace _6.图
{
	public sealed class 邻接表表示法
	{

		//邻接点
		class ArcNode
		{
			//邻接点序号
			int AdjVex;
			//下一个节点
			ArcNode NextArc;

			//【十字链表】
			////弧尾（箭尾）
			//int TailVex;
			////弧头(箭头指向)
			//int HeadVex;
			////下一个指向其他的（记录出度）
			//ArcNode TLink;
			////下一个指向自己的（记录入读）
			//ArcNode HLink;


			//其他属性（如权值）
			int Wegiht;
		}

		//顶点结构
		class VertexNode
		{
			char Data;
			//第一个邻接点(记录出度)
			ArcNode FirstOut;

			//第一个临接点（记录入度），解决有向图使用邻接表计算入读困难问题
			//【十字链表】
			//ArcNode FristIn;
		}

		class ALGragh
		{
			VertexNode[] Vertices;
			//图的当前的点数目
			int VexCount;
			//图当前边的数目
			int ArcCount;
		}









		public void Test()
		{

			//特点：
			//邻接表不唯一（顺序可以变）
			//若【无向图】中有n个顶点，e条边，则邻接表需要n个头节点和2e个表节点。适合存储稀疏图。空间复杂度O（n+2e）
			//【无向图】中顶点【vi的度】为【第i个单链表】中的【节点数】

			//若【有向图】中有n个顶点，e条边，则邻接表需要n个头节点和e个表节点。空间复杂度O（n+e）
			//计算vi的【出度】为【第i个单链表】中的【节点数】
			//计算vi的【入度】为除自身外的每个【单链表包含vi】的个数
			//【邻接表】存储有向图，找【出度】容易，【入度】难
			//可以用【逆邻接表】存储入度边
			//【逆邻接表】存储有向图，找【入度】容易，【出度】难
			//【十字链表】解决存储有向图找【出度】难

			//优点：
			//方便找任一顶点所有【邻接点】
			//节约稀疏图空间，空间复杂度O（n+2e）
			//计算任意顶点的度？
			//对于【无向图】方便
			//缺点：
			//对于【有向图】只能方便计算出度，需要构造【逆邻接表】来方便计算【入度】
			//不方便检查任意对顶点间是否存在边

		}

	}
}
